AlgorithmsBranch and Bound

Branch-and-Bound with the 0-1 Knapsack problem(Best-First Search)(0-1 배낭 문제-최고우선탐색)

0-1 배낭 문제, 분기한정법, 알고리즘

In general, the breadth-first search strategy has no advantage over a depth-first search (backtracking). However, we can improve our search by using our bound to do more than just determine whether a node is promising. After visiting all the children of a given node, we can look at all the promising, unexpanded nodes and expand beyond the one with the best bound. Recall that a node is promising if its bound is better than the value of the best solution found so far. In this way, we often arrive at an optimal solution more quickly than if we simply proceeded blindly in a predetermined order. The example that follows illustrates this method.

0-1 배낭 문제에 최고우선탐색을 적용하기에 앞서 깊이우선탐색(백트래킹)과 너비우선탐색으로 해결하는 법을 살펴봤다. 일반적으로 너비우선탐색은 깊이우선탐색보다 좋은 점이 없었다. 하지만 최고우선탐색에서는 bound 값을 노드의 유망성 여부를 판단하는 것 외에 추가적으로 사용하여 알고리즘의 효율을 향상시킨다.

최고우선탐색은 어떤 노드의 모든 자식노드를 방문한 후 유망하면서 미확장된 노드 모두를 살펴보고 그 중 bound 값이 가장 좋은 노드를 우선으로 확장한다. 지금까지 찾은 최고의 해답보다 그 bound 값이 더 좋다면 그 노드는 유망하다. 이렇게 하면 미리 결정된 순서(깊이우선탐색, 너비우선탐색)대로 탐색을 진행하는 것보다 더 빨리 최적 해를 찾게된다.

Example Suppose that n = 4, W = 16, and we have the following:

i $p_i$ $w_i$ $p_i / w_i$
1 $40 2 $20
2 $30 5 $6
3 $50 10 $5
4 $10 5 $2

[The pruned state space tree produced using best-first search in above Example. Stored at each node from top to bottom are the total profit of the items stolen up to that node, their total weight, and the bound on the total profit that could be obtained by expanding beyond the node. The node shaded in color is the one at which an optimal solution is found.]

Step 1 루트노드(0,0)를 방문한다.

[profit = 0], [weight = 0], [bound = 115(= 40 + 30 + (16 - 7) x 50/10)]
maxprofit = 0

Step 2 노드(1,1)을 방문한다.

[profit = 40], [weight = 2], [bound = 115]
(2 <= 16(W)) && (40 > 0(current maxprofit)) → maxprofit = 40

Step 3 노드(1,2)를 방문한다.

[profit = 0], [weight = 0], [bound = 82(= 30 + 50 + (16 - 15) x 10/5)]
(0 <= 16(W)) && (0 > 40(current maxprofit)) → false

Step 4 아직 확장하지 않은 노드 중에서 가장 큰 bound를 가진 유망한 노드를 찾는다. 노드(1,1) bound = 115 > 노드(1,2) bound = 82 이므로, 노드(1,1)이 bound가 가장 크면서 유망하고 확장하지 않은 노드이다. 따라서 그 노드의 자식노드(2,1)를 다음으로 방문한다.

Step 5 노드(2,1)을 방문한다.

[profit = 70], [weight = 7], [bound = 115]
(7 <= 16(W)) && (70 > 40(current maxprofit)) → maxprofit = 70

Step 6 노드(2,2)를 방문한다.

[profit = 40], [weight = 2], [bound = 98(= 40 + 50 + (16 - 12) x 10/5)]
(2 <= 16(W)) && (40 > 70(current maxprofit)) → false

Step 7 아직 확장하지 않은 노드 중에서 가장 큰 bound를 가진 유망한 노드를 찾는다. 노드(2,1) bound = 115 > 노드(2,2) bound = 98 > 노드(1,2) bound = 82 이므로 노드(2,1)의 자식노드인 (3,1)를 다음으로 방문한다.

Step 8 노드(3,1)을 방문한다.

[profit = 120], [weight = 17], [bound = 0]
(17 <= 16(W)) && (120 > 70(current maxprofit)) → false
weight가 W를 초과했으므로 bound 값을 0으로 놓아 유망하지 않다고 표시한다.

Step 9 노드(3,2)를 방문한다.

[profit = 70], [weight = 7], [bound = 80(= 40 + 30 + 10]
(7 <= 16(W)) && (70 > 70(current maxprofit)) → false

Step10 아직 확장하지 않은 노드 중에서 가장 큰 bound를 가진 유망한 노드를 찾는다. 노드(2,2) bound = 98 > 노드(1,2) bound = 82 > 노드(3,2) bound = 80 이므로 노드(2,2)의 자식노드인 (3,3)을 다음으로 방문한다.

Step11 노드 (3,3)을 방문한다.

[profit = 90], [weight = 12], [bound = 98(= 40 + 50 + (16 - 12) x 10/5)]
(12 <= 16(w)) && (90 > 70(current maxprofit)) → maxprofit = 90
82(=노드(1,2) bound) <= 90 → 이 시점에서 노드(1,2)는 유망하지 않다고 결정한다.
80(=노드(3,2) bound) <= 90 → 이 시점에서 노드(3,2)는 유망하지 않다고 결정한다.

Step12 노드(3,4)를 방문한다.

[profit = 40], [weight = 2], [bound = 50(= 40 + 10)]
(2 <= 16(W)) && (40 > 90(current maxprofit)) → false
50(=노드(3,4) bound) <= 90 → 노드(3,4)는 유망하지 않다고 결정한다.

Step13 아직 확장하지 않은 노드 중에서 가장 큰 bound를 가진 유망한 노드를 찾는다. 유일하게 확장되지 않고 남은 유망한 노드는 (3,3)이다. 그 노드의 자식노드인 (4,1)을 다음으로 방문한다.

Step14 노드(4,1)을 방문한다.

[profit = 100], [weight = 17], [bound = 0]
(17 <= 16(W)) && (100 > 90(current maxprofit)) → false
weight가 W를 초과했으므로 bound 값을 0으로 놓아 유망하지 않다고 표시한다.

Step15 노드(4,2)를 방문한다.

[profit = 90], [weight = 12], [bound = 90(= 40 + 50)]
(12 <= 16(W)) && (90 > 90(current maxprofit)) → false
90(=노드(4,2) bound) <= 90 → 노드(4,2)는 유망하지 않다고 결정한다.

Step16 Because there are now no promising, unexpanded nodes, we are done.

상태공간트리에서 잎노드들은 그 bound 값이 maxprofit을 넘을 수 없으므로 자동으로 유망하지 않게 된다. 유망하면서 미확장된 노드가 없으므로 알고리즘이 종료된다.

It must be stressed, however, that there is no guarantee that the node that appears to be best will actually lead to an optimal solution. In Example, node (2,1) appears to be better than node (2,2), but node (2,2) leads to the optimal solution. In general, best-first search can still end up creating most or all of the state space tree for some instances.

위의 예제에서 노드(2,1)이 노드(2,2)보다 더 좋아보였지만 노드(2,2)가 해답을 이끌어낸다. 즉, 최고라고 여겨지는 노드에서 최적의 해가 나온다는 보장은 없다.


The Best-First Search with Branch-and-Bound Pruning Algorithm for the 0-1 Knapsack Problem

Algorithm Design

$$
\begin{align}
totweight &= weight + \sum_{j=i+1}^{k-1}w_j \\
bound &= \left(profit + \sum_{j=i+1}^{k-1}p_j\right) + (W - totweight) \times \frac{w_k}{p_k}
\end{align}
$$

  • profit: the sum of the profits of the items included up to the node.
  • weight: the sum of the weights of those items.
  • totweight: the sum of the weights could be obtained by expanding beyond that node (W를 초과할 수 없다.)
  • bound: the upper bound on the profit that could be obtained by expanding beyond that node.

Recall that a node is also nonpromising if

$$
weight <= W
$$

The implementation of best-first search consists of a simple modification to breadth-first search. Instead of using a queue, we use a priority queue.

너비우선탐색을 조금 변형하면 최고우선탐색을 구현할 수 있다. 최고의 bound 값을 가진 노드를 우선적으로 선택하기 위해 단순 큐 대신 우선순위 큐(Priority Queue)가 사용된다.

Besides using a priority queue instead of a queue, we have added a check following the removal of a node from the priority queue. The check determines if the bound for the node is still better than best. This is how we determine that a node has become nonpromising after visiting the node. For example, node (1, 2) is promising at the time we visit it. In our implementation, this is when we insert it in PQ. However, it becomes nonpromising when maxprofit takes the value 90. In our implementation, this is before we remove it from PQ. We learn this by comparing its bound with maxprofit after removing it from PQ. In this way, we avoid visiting children of a node that becomes nonpromising after it is visited.

우선순위 큐에서 노드를 제거한 후 노드의 bound 값이 maxprofit 보다 아직 좋은지를 결정하는 검사를 추가했다. 예를 들어 노드 (1,2)는 방문 당시에는 유망하지만, 노드(3,3)을 방문하면서 maxprofit 값이 90이 될 때 유망하지 않게 된다. 이런식으로 더 이상 유망하지 않은 노드의 자식노드를 방문하지 못하게 한다.

Pseudo Code

void best_first_branch_and_bound (state_space_tree T, number& best)
{
  priority_queue_of_node PQ;
  node u, v;
  initialize(PQ); // Initialize PQ to empty
  v = root of T;
  best = value(v);
  insert(PQ,v);
  while(!empty(PQ)) // Remove node with best bound
  {
    remove(PQ,v);
    if (bound(v) is better than best) // Check if node is still promising
    {   
      for (each child u of v)
      {   
        if (value(u) is better than best)
          best = value(u);
        if (bound(u) is better than best)
          insert(PQ,u);
      }
    }
  }
}

Source Code

// File: knapsack_bestfs.h
#ifndef KNAPSACK_BESTFS_H
#define KNAPSACK_BESTFS_H
#include "pqueue.h"  // Provides priority_queue
using namespace data_structures; // for node

namespace algorithms
{
  void knapsack3(int n, const int p[ ], const int w[ ], int W, int& maxprofit);
  // Problem: Let n items be given, where each item has a weight and
  // a profit. The weights and profits are positive integers. Furthermore,
  // let a positive integer W be given. Determine a set of items with
  // maximum total profit, under the constraint that the sum of their
  // weights cannot exceed W .
  // Inputs: positive integers n and W , arrays of positive integers
  // w and p, each indexed from 1 to n, and each of which is sorted in
  // nonincreasing order according to the values of p[i] / w [i].
  // Outputs: an integer maxprofit that is the sum of the profits in an
  // optimal set.

  float bound(node u, int n, const int p[ ], const int w[ ], int W);
}

#endif
// File: knapsack_bestfs.cpp
#include <cassert> // Provides assert
#include <iostream> // Provides cout and endl
#include <iomanip>
#include "knapsack_bestfs.h"
using namespace std;

namespace algorithms
{
  void knapsack3(int n, const int p[ ], const int w[ ], int W, int& maxprofit)
  {
    int prm_node_cnt = 0; // The number of promising nodes
    int nprm_node_cnt = 0; // The number of non-promising nodes
    priority_queue PQ;
    node u, v;

    assert(PQ.is_empty( )); // Initialize PQ to be empty.
    v.level = 0; v.profit = 0; v.weight = 0; // Initialize v to be the root.
    maxprofit = 0;
    v.bound = bound(v, n, p, w, W);
    PQ.insert(v);

    while (!PQ.is_empty( ))
    {
      v = PQ.get_front( ); // Remove node with best bound.

      cout << "level: "  << setw(1) << v.level  << setw(10)
           << "profit: " << setw(2) << v.profit << setw(10)
           << "weight: " << setw(2) << v.weight << setw(10)
           << "bound: "  << setw(2) << v.bound  << endl;

      if (v.bound > maxprofit) // Check if node is still promising.
      {
        // Set u to the child that includes the next item.
        u.level = v.level + 1;
        u.weight = v.weight + w[u.level];
        u.profit = v.profit + p[u.level];

        if (u.weight <= W && u.profit > maxprofit)
          maxprofit = u.profit;

        u.bound = bound(u, n, p, w, W);

        if (u.bound > maxprofit)
          PQ.insert(u);
        else
        {
          // Count the number of non-promising nodes
          ++nprm_node_cnt;
        }

        // Set u to the child that does not include the next item.
        u.weight = v.weight;          
        u.profit = v.profit;            
        u.bound = bound(u, n, p, w, W);

        if (u.bound > maxprofit)
          PQ.insert(u);
        else
        {
          // Count the number of non-promising nodes
          ++nprm_node_cnt;
        }

        // Count the number of promising nodes
        ++prm_node_cnt;   
      }
      else
      {
        // Count the number of non-promising nodes
        ++nprm_node_cnt;
      }
    }
    cout << endl << "The number of promising node: " << prm_node_cnt << endl;
    cout << "The number of non-promising node: " << nprm_node_cnt << endl;
  }

  float bound(node u, int n, const int p[ ], const int w[ ], int W)
  {
    int j, k;
    int totweight;
    float result;

    if (u.weight >= W)
      return 0;
    else
    {
      result = (float)u.profit;
      j = u.level + 1;
      totweight = u.weight;
      while (j <= n && totweight + w[j] <= W)
      {
        // Grab as many items as possible.
        totweight = totweight + w[j];
        result = result + p[j];
        ++j;
      }
      k = j; // Use k for consistency with formula in text.
      if (k <= n) // Grab fraction of kth item.
        result = result + (W - totweight) * (p[k] / w[k]);

      return result;
    }
  }
}
// File: maxtotprofit.cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "knapsack_bestfs.h"
using namespace std;
using namespace algorithms;

const int n = 4;
const int W = 16;
int w[n+1] = {0, 2, 5, 10, 5}; // w[0] is meaningless
int p[n+1] = {0, 40, 30, 50, 10}; // p[0] is meaningless

int main( )
{
  clock_t start, end;
  int maxprofit = 0;

  start = clock( );
  knapsack3(n, p, w, W, maxprofit);
  end = clock( );

  cout << "The answer: " << maxprofit << endl;
  double result = (double)(end-start) / CLOCKS_PER_SEC;
  cout << "Elpased time is: "<< result << " sec." << endl;

  return EXIT_SUCCESS;
}


Time Complexity Analysis

Worst-Case Time Complexity

  • $O(n) = 1 + 2 + 2^2 + 2^3 + … + 2^n = 2^{(n+1)} - 1 \in \Theta(2^n)$

$w_i$를 포함시키느냐 그렇지 않느냐의 두 가지 선택이므로 상태공간트리 내 전체 노드의 수는 최대 $2^{n+1} - 1$개가 된다. 최악의 경우 방문하는 노드의 수가 지수이지만, 가지치기를 통해 상태노드의 수를 줄일 수 있기 때문에 알고리즘의 효율은 더 좋을 수 있다.

Comparing the Algorithm Techniques for the 0-1 Knapsack Problem

Problem Algoritm Technique Worst-Case Time Complexity Checking Nodes
0-1 Knapsack Problem Dynamic Programming $O(min(2^n, nW))$
0-1 Knapsack Problem Backtracking(depth-first search)
In backtracking algorithms the worst case gives little insight into how many checking is usually saved by backtracking.		 $\Theta(2^n)$ 13
0-1 Knapsack Problem Branch-and-Bound(breadth-first search)
In general, the breadth-first search strategy has no advantage over a depth-first search(backtracking).		 $\Theta(2^n)$ 17
0-1 Knapsack Problem Branch-and-Bound(best-first search)
The best-first search can arrive at an optimal solution faster than we would by methodically visiting the nodes in some predetermined order (such as a dfs, bfs).		 $\Theta(2^n)$ 11

Using best-first search, we have checked only 11 nodes, which is 6 less than the number checked using breadth-first search and 2 less than the number checked using depth-first search. A savings of 2 is not very impressive; however, in a large state space tree, the savings can be very significant when the best-first search quickly hones in on an optimal solution.

같은 예제에서 너비우선탐색은 17개, 깊이우선탐색은 13개의 노드 수를 검사하는 반면 최고우선탐색은 총 11개의 노드를 검사한다. 2개 노드를 절약한 건 인상적이지 않지만 큰 상태공간트리에서 최고우선탐색으로 최적해를 빨리 찾는 경우 이 차이는 매우 중요하다.

일반적으로 0-1 배낭 문제에 대해 너비우선탐색(13개 노드 검사)의 효율이 깊이우선탐색(17개 노드 검사)보다 더 좋다고 단정지을 순 없다. 깊이우선탐색과 너비우선탐색 중 무엇이 더 효율적이냐에 대한 답은 문제마다 다르기 때문이다.

nW 덕분에 동적계획 알고리즘으로 문제를 해결하는게 더 좋은 것처럼 보일 수 있다. 그러나 깊이우선탐색, 너비우선탐색, 최고우선탐색 알고리즘에서 최악의 경우를 따지면 실제 방문하는 노드의 수를 얼마나 절약했는지 반영이 안되므로, 알고리즘의 상대적인 효율을 이론적으로 분석하기는 어렵다.

Share